In a computer system, a cache stores data in order to decrease data retrieval times for a processor. More particularly, a cache stores specific subsets of data in high-speed memory. When a processor requests a piece of data, the system checks the cache first to see if the data is stored within the cache. If it is available, the processor can retrieve the data much faster than if the data was stored in other computer readable media such as random access memory, a hard drive, CD ROM or floppy disk.
One particular type of cache is referred to as a trace cache. A trace cache is responsible for building, caching, and delivering instruction traces to a processor. In one type of trace cache, instructions are stored as "traces" of decoded micro-operations or "micro-ops", and are only allowed to be accessed in units of "traces." Traces are blocks of micro-op instructions that are distinguishable from one another only by their trace heads. Generally, traces may be terminated upon encountering an indirect branch or by reaching one of many preset threshold conditions, such as the number of conditional branches in the trace or the number of total micro-ops in the trace.
A problem associated with the trace cache is branch prediction. It can be appreciated that some micro-ops contain conditional branches to determine whether an algorithm should perform one set of instructions under certain conditions and another set of instructions under a different set of conditions. To minimize processing cycles, modem central processing units (CPU), such as Pentium.TM. and Pentium Pro.TM. microprocessors produced by Intel, attempt to predict the targets of branches in instructions. If the CPU mispredicts which target is selected, the CPU must utilize extra CPU cycles to correct the misprediction. This is referred to as a branch misprediction penalty. Because of the structure of the trace cache, the problem of branch predictions is aggravated over conventional systems.